#include <bits/stdc++.h>
using namespace std;
int n, k, m, f[101][101];
int color[101];
int ans = 0;
bool check(int x)
{
	for(int i = 1; i < x; i++)
	{
		if(f[x][i] == 1 && color[x] == color[i]) 
			return 0;
	}
	return 1;
}
void dfs(int x)
{
	if(x > n) {
		ans++;
		return ;
	}
	for(int i = 1; i <= m; i++) {
		color[x] = i;
		if(check(x))
			dfs(x + 1);
		else
			color[x] = 0;
	}
}
int main()
{	
    cin >> n >> k >> m;
    for (int i = 1; i <= k; i++) {
        int a, b;
        cin >> a >> b;
        f[a][b] = 1;
        f[b][a] = 1;
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}